// see https://stackfull.dev/tree-data-structure-in-javascript

/**
 * 二叉树节点类型
 * @param val
 */
function TreeNode(val) {
  this.val = val
  this.left = null
  this.right = null
}

// 基本使用
const root = new TreeNode(1)
const node2 = new TreeNode(2)
const node3 = new TreeNode(3)
const node4 = new TreeNode(4)
const node5 = new TreeNode(5)
node2.left = node4
node2.right = node5
root.left = node2
root.right = node3

/**
 * 前序遍历
 * @param root
 * @returns
 */
function walkPreOrder(root) {
  if (root === null) return

  // 递归
  //   console.log(root.val)

  //   if (root.left) walkPreOrder(root.left)
  //   if (root.right) walkPreOrder(root.right)

  //   栈
  const stack = [root]
  while (stack.length) {
    const item = stack.pop()

    console.log(item)

    if (item.right) stack.push(item.right)
    if (item.left) stack.push(item.left)
  }
}

walkPreOrder(root)

/**
 * 中序遍历
 * @param root
 * @returns
 */
function walkInOrder(root) {
  if (root === null) return

  //   if (root.left) walkInOrder(root.left)

  //   console.log(root.val)

  //   if (root.right) walkInOrder(root.right)

  const stack = []
  let current = root

  while (stack.length || current) {
    while (current) {
      stack.push(current)
      current = current.left
    }
    const last = stack.pop()

    console.log(last.val)

    current = last.right
  }
}

walkInOrder(root)
// 4 2 5 1 3

/**
 * 后续遍历
 * @param root
 * @returns
 */
function walkPostOrder(root) {
  if (root === null) return

  if (root.left) walkPostOrder(root.left)
  if (root.right) walkPostOrder(root.right)

  console.log(root.val)
}

walkPostOrder(root)
// 4 5 2 3 1
